UVa/10249 - The grand dinner/10249.2.cpp

   1 /*
   2   Problem: 10249 - The grand dinner
   3   Andrés Mejía-Posada (andmej@gmail.com)
   4
   5   Time limit exceeded
   6  */
   7 using namespace std;
   8 #include <algorithm>
   9 #include <iostream>
  10 #include <iterator>
  11 #include <sstream>
  12 #include <fstream>
  13 #include <cassert>
  14 #include <climits>
  15 #include <cstdlib>
  16 #include <cstring>
  17 #include <string>
  18 #include <cstdio>
  19 #include <vector>
  20 #include <cmath>
  21 #include <queue>
  22 #include <deque>
  23 #include <stack>
  24 #include <list>
  25 #include <map>
  26 #include <set>
  27
  28 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  29 #define D(x) cout << #x " is " << x << endl
  30 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  31
  32 const int MAXN = 135;
  33
  34 int cap[MAXN][MAXN];
  35 int flow[MAXN][MAXN];
  36 int prev[MAXN];
  37
  38 vector<int> g[MAXN];
  39
  40 bool findPath(int n, int src, int sink){
  41   fill(prev, prev+n, -1);
  42   queue<int> q;
  43   q.push(src);
  44   while (q.size()){
  45     int u = q.front(); q.pop();
  46     if (u == sink) return true;
  47     foreach(k, g[u]){
  48       int v = *k;
  49       if (v != src && prev[v] == -1 && flow[u][v] < cap[u][v]){
  50         prev[v] = u;
  51         q.push(v);
  52       }
  53     }
  54   }
  55   return false;
  56 }
  57
  58 int maxFlow(int n, int src, int sink){
  59   memset(flow, 0, sizeof flow);
  60   int ans = 0;
  61   while (findPath(n, src, sink)){
  62     int neck = INT_MAX;
  63     for (int u = sink; prev[u] != -1; u = prev[u]){
  64       neck = min(neck, cap[prev[u]][u] - flow[prev[u]][u]);
  65     }
  66     for (int u = sink; prev[u] != -1; u = prev[u]){
  67       flow[prev[u]][u] += neck;
  68       flow[u][prev[u]] -= neck;
  69     }
  70     ans += neck;
  71   }
  72   return ans;
  73 }
  74
  75 inline void add_edge(int u, int v, int c){
  76   g[u].push_back(v); g[v].push_back(u); cap[u][v] = c;
  77 }
  78
  79 void bigcase(){
  80   int m = 50, n = 50;
  81   printf("%d %d\n", m, n);
  82   for (int i=0; i<m; ++i){
  83     printf("%d ", 100);
  84   }puts("");
  85   for (int i=0; i<n; ++i){
  86     printf("%d ", 100);
  87   }puts("");
  88
  89 }
  90
  91 int main(){
  92   //bigcase(); return 0;
  93   int nteams, ntables;
  94   while (scanf("%d %d", &nteams, &ntables)==2 && nteams && ntables){
  95     int people = 0, spots = 0;
  96     const int source = nteams + ntables, sink = source + 1;
  97     for (int i=0; i<=sink; ++i) g[i].clear();
  98     memset(cap, 0, sizeof cap);
  99     for (int i=0, c; i<nteams; ++i){
 100       scanf("%d", &c);
 101       add_edge(source, i, c);
 102       people += c;
 103     }
 104     for (int i=0, c; i<ntables; ++i){
 105       scanf("%d", &c);
 106       add_edge(nteams+i, sink, c);
 107       spots += c;
 108     }
 109     if (people > spots){ printf("0\n"); continue; }
 110     for (int i=0; i<nteams; ++i){
 111       for (int j=0; j<ntables; ++j){
 112         add_edge(i, nteams+j, 1);
 113       }
 114     }
 115     int f = maxFlow(nteams + ntables + 2, source, sink);
 116     if (f < people){
 117       printf("0\n");
 118     }else{
 119       printf("1\n");
 120       for (int i=0; i<nteams; ++i){
 121         bool first = true;
 122         foreach(v, g[i]){
 123           int j = *v;
 124           if (flow[i][j] > 0){
 125             if (!first) printf(" ");
 126             first = false;
 127             printf("%d", j-nteams+1);
 128           }
 129         }
 130         printf("\n");
 131       }
 132     }
 133   }
 134   return 0;
 135 }